Concept(s)-clé(s) et théorie

Définition 1

Soient $A \in \mathcal{M}_{m \times n}(\mathbb{R})$, $b \in \mathcal{M}_{m \times 1}(\mathbb{R})$ et $X = \left(x_1, \dots, x_n\right)^T$. Aussi, désignons par $\phi: \mathbb{R}^n \rightarrow \mathbb{R}^m$ l'application linéaire associée à $A$. Une solution du système $\boldsymbol{AX=b}$ au sens du moindres carrées est une solution du systeme

\begin{equation} AX = proj_{Im(\phi)}b \end{equation}

Théorème 1

Soient $A \in \mathcal{M}_{m \times n}(\mathbb{R})$, $b \in \mathcal{M}_{m \times 1}(\mathbb{R})$ et $X = \left(x_1, \dots, x_n\right)^T$. Alors une solution du système $AX=b$ au sens du moindres carrées est une solution du système $A^TAX = A^Tb$.

Exercises et Examples

import Librairie.AL_Fct as al
import Corrections.corrections as corrections
import numpy as np
import sympy as sp

Exercice 1

Considérez les systèmes linéaires suivants, avec forme $Ax=b$. Calculez leur solution au sens des moindres carrés en projetant $b$ sur l'espace image de $A$ et en résolvant $Ax = proj_{Im(A)}b$.

1. $\quad A = \begin{pmatrix}1 & 0 \\ 1 & 0\end{pmatrix} \qquad \qquad b = \begin{pmatrix}1 \\ 3\end{pmatrix}$
2. $\quad A = \begin{pmatrix}1 & 1 \\ 1 & -1 \\ 2 & 0\end{pmatrix} \qquad \qquad b = \begin{pmatrix}1 \\ 2 \\ -2\end{pmatrix}$
3. $\quad A = \begin{pmatrix}1 & 0 & 0\\ 0 & 1 & 1 \\ 1 & 0 & 0\end{pmatrix} \qquad \quad \ \ b = \begin{pmatrix}-1 \\ 2 \\ 1\end{pmatrix}$
4. $\quad A = \begin{pmatrix}1 & 0 & 1\\ -1 & 1 & -1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ -1 & 0 & 1\end{pmatrix} \qquad \ \ b = \begin{pmatrix}0 \\ 2 \\ 0 \\ 1 \\ 4\end{pmatrix}$

Aide

Pour calculer la projection orthogonal de $b$ sur $Im(A)$, il peut être utile de dériver une base ortogonale (ou orthonormée) pour ce dernier. Vous pouvez utiliser la cellule suivante pour exécuter l'algorithme interactif de Gram-Schmidt.

Instructions

Pour utiliser la méthode interactive de Gram-Schmidt, procédez comme suit:

1. Insérez le numéro du cas souhaité dans la cellule suivante. Exécutez le cellules appelées "SÉLECTION DU CAS" et "INITIALISATION DES VARIABLES"
2. Exécutez la cellule appelée "SÉLECTION DES PARAMÈTRES" pour sélectionner le type d'opération et les coefficients nécessaires
3. Exécutez la cellule appelée "EXÉCUTER L'ÉTAPE DE L'ALGORITHME GRAM-SCHMIDT" pour exécuter l'étape de l'algorithme de Gram-Schmidt avec les paramètres précédemment sélectionnés
4. Répétez les étapes 2 et 3 jusqu'à ce que l'algorithme soit terminée

En outre:

1. Vous pouvez annuler une opération en sélectionnant le bouton "Revert".

2. Si les coefficients insérés sont incorrects, vous pouvez essayer avec de nouvelles valeurs sans effectuer une opération "Revert".

3. Les coefficients qui ne sont pas liés à l'opération sélectionnée peuvent être définis sur n'importe quelle valeur, car ils ne sont pas utilisés dans le code.

# SÉLECTION DU CAS
case_number = 1 # CHOISISSEZ LE NUMÉRO DE CAS ICI ET EXECUTEZ LA CELLULE SUIVANTE!

# INITIALISATION DES VARIABLES
if case_number == 1:
    A_cols = [[1,1], [0,0]]
    A = np.array(A_cols).T
    b = [1,3]
    dim=2
elif case_number == 2:
    A_cols = [[1,1,2], [1,-1,0]]
    A = np.array(A_cols).T
    b = [1,2,-2]
    dim=2
elif case_number == 3:
    A_cols = [[1,0,1], [0,1,0], [0,1,0]]
    A = np.array(A_cols).T
    b = [-1,2,1]
    dim=3
elif case_number == 4:
    A_cols = [[1,-1,0,1,-1], [0,1,1,1,0], [1,-1,1,0,1]]
    A = np.array(A_cols).T
    b = [0,2,0,1,4]
    dim=3
else:
    print(f"{case_number} n'est pas un numéro de cas valide!" 
          f"Numéros de cas disponibles: [1,2,3,4]")

step = 0
VectorsList = [A_cols]

# SÉLECTION DES PARAMÈTRES
print(f"Current vectors: {A_cols}")
norm_coeff, proj_coeffs, operation, step_number = al.manual_GS(dim=dim)

Current vectors: [[1, 1], [0, 0]]

# EXÉCUTER L'ÉTAPE DE L'ALGORITHME GRAM-SCHMIDT
A_cols = al.interactive_gram_schmidt(norm_coeff, proj_coeffs,
                                     operation, step_number, 
                                     A_cols.copy(), VectorsList)

Procédé de Gram–Schmidt

Étape : Étape 1Étape 2

Coefficient de projection 1 :

Coefficient de normalisation : Vérifier cette étape Solution

Correct !

Incorrect. Vérifiez les coefficients de projection et la norme.

Coefficients attendus

1. Étape 1 : projections = [], norme = 1.414
2. Étape 2 : projections = [0.0], norme = 0

Base orthonormée obtenue : [[0.7071, 0.7071], [0.0, 0.0]]

Aide

Pour résoudre le système linéaire, vous pouvez tirer parti des cellules interactives suivantes qui permettent d'appliquer la méthode d'élimitation de Gauss. Notez que vous devez entrer la valeur trouvée pour la projection de $\boldsymbol{b}$ sur l'espace image de $\boldsymbol{A}$ dans la première ligne!

proj_b = [[2], [2]]  # INSEREZ ICI LA VALEUR TROUVÉE POUR LA PROJECTION DE b SUR Im (A)
al.printA(A, proj_b)
[i,j,r,alpha]= al.manualEch(A,proj_b)
m=np.concatenate((A,proj_b), axis=1)
MatriceList=[A]
RhSList=[proj_b]

$\left(\begin{array}{cc| cc} 1 & 0 & 2 \\1 & 0 & 2 \end{array}\right)$

Régler les paramètres et cliquer sur Effectuer. Répéter jusqu'à obtenir une forme échelonnée réduite.

Opération :
T_ij  (échange lignes i et j)
D_i(α)  (multiplie ligne i par α)
L_ij(α)  (ajoute α×ligne j à ligne i)
Revert  (annuler la dernière opération)

Ligne i :    Ligne j :

Coeff. α :

Effectuer l'opération

Impossible de revenir sur l'opération !

Indices hors limites (1..2).

α doit être non-nul.

m=al.echelonnage(i,j,r,alpha,A,m,MatriceList,RhSList)

Régler les paramètres et cliquer sur Effectuer. Répéter jusqu'à obtenir une forme échelonnée réduite.

Opération :
T_ij  (échange lignes i et j)
D_i(α)  (multiplie ligne i par α)
L_ij(α)  (ajoute α×ligne j à ligne i)
Revert  (annuler la dernière opération)

Ligne i :    Ligne j :

Coeff. α :

Effectuer l'opération

Impossible de revenir sur l'opération !

Indices hors limites (1..2).

α doit être non-nul.

# INSEREZ ICI LA SOLUTION
x, y = sp.symbols('x, y')
sol = sp.sets.FiniteSet((2, y))

#  ÉVALUATION DE LA SOLUTION
corrections.Ex1_Chapitre9_12(sol, case_nb=case_number)

C'est correct!

Le systéme n'admet pas des solutions!

La solution du système peut être exprimée comme une solution au sens du moindres carrés.

Exercice 2

Considérez les systèmes linéaires suivants, avec forme $Ax = b$. Calculez leur solution au sens des moindres carrés en résolvant le système linéaire $A^TAx=A^Tb$.

1. $\quad A = \begin{pmatrix}0 & 1 \\ 0 & -1\end{pmatrix} \qquad \qquad b = \begin{pmatrix}0 \\ 2\end{pmatrix}$
2. $\quad A = \begin{pmatrix}0 & 1 \\ 1 & 1 \\ 1 & -2\end{pmatrix} \qquad \qquad \ \ b = \begin{pmatrix}1 \\ 1 \\ 0\end{pmatrix}$
3. $\quad A = \begin{pmatrix}0 & 1 & 0\\ 1 & 0 & 1 \\ -2 & 0 & 0\end{pmatrix} \qquad \quad b = \begin{pmatrix}0 \\ 2 \\ -1\end{pmatrix}$
4. $\quad A = \begin{pmatrix}1 & 0 & 0\\ 1 & -1 & -1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & -1\end{pmatrix} \qquad \ \ b = \begin{pmatrix}2 \\ 0 \\ 0 \\ -1 \\ -1\end{pmatrix}$

# SÉLECTION DU CAS
case_number = 1 # CHOISISSEZ LE NUMÉRO DE CAS ICI ET EXECUTEZ LA CELLULE SUIVANTE!

# INITIALISATION DES VARIABLES
if case_number == 1:
    A_cols = [[0,0], [1,-1]]
    A = np.array(A_cols).T
    b = [[0], [2]]
elif case_number == 2:
    A_cols = [[0,1,1], [1,1,-2]]
    A = np.array(A_cols).T
    b = [[1], [1], [0]]
elif case_number == 3:
    A_cols = [[0,1,-2], [1,0,0], [0,1,0]]
    A = np.array(A_cols).T
    b = [[0], [2], [-1]]
elif case_number == 4:
    A_cols = [[1,1,0,1,0], [0,-1,1,0,1], [0,-1,0,0,-1]]
    A = np.array(A_cols).T
    b = [2,0,0,-1,-1]
else:
    print(f"{case_number} n'est pas un numéro de cas valide!" 
          f"Numéros de cas disponibles: [1,2,3,4]")

Aide

Pour résoudre le système linéaire, vous pouvez tirer parti des cellules interactives suivantes qui permettent d'appliquer la méthode d'élimitation de Gauss.

al.printA(A.T@A, A.T@np.array(b))
[i,j,r,alpha]= al.manualEch(A.T@A, A.T@np.array(b))
m=np.concatenate((A.T@A,A.T@np.array(b)), axis=1)
MatriceList=[A.T@A]
RhSList=[A.T@np.array(b)]

$\left(\begin{array}{cc| cc} 0 & 0 & 0 \\0 & 2 & -2 \end{array}\right)$

Régler les paramètres et cliquer sur Effectuer. Répéter jusqu'à obtenir une forme échelonnée réduite.

Opération :
T_ij  (échange lignes i et j)
D_i(α)  (multiplie ligne i par α)
L_ij(α)  (ajoute α×ligne j à ligne i)
Revert  (annuler la dernière opération)

Ligne i :    Ligne j :

Coeff. α :

Effectuer l'opération

Impossible de revenir sur l'opération !

Indices hors limites (1..2).

α doit être non-nul.

m=al.echelonnage(i,j,r,alpha,A.T@A,m,MatriceList,RhSList)

Régler les paramètres et cliquer sur Effectuer. Répéter jusqu'à obtenir une forme échelonnée réduite.

Opération :
T_ij  (échange lignes i et j)
D_i(α)  (multiplie ligne i par α)
L_ij(α)  (ajoute α×ligne j à ligne i)
Revert  (annuler la dernière opération)

Ligne i :    Ligne j :

Coeff. α :

Effectuer l'opération

Impossible de revenir sur l'opération !

Indices hors limites (1..2).

α doit être non-nul.

# INSEREZ ICI LA SOLUTION
x,y,z = sp.symbols('x, y, z')
sol = sp.sets.FiniteSet((x,-1)) 

# ÉVALUATION DE LA SOLUTION
corrections.Ex2_Chapitre9_12(sol, case_nb=case_number)

C'est correct!

Le systéme n'admet pas des solutions!

La solution du système peut être exprimée comme une solution au sens du moindres carrés.

Exercice 3

Un scénario important dans lequel le calcul des solutions de systèmes linéaires au sens des moindres carrés est utilisé est celui de la régression linéaire. Supposons que l'on donne $N$ mesures de certaines quantités $\left\{\left\{x_j^i\right\}_{j=1}^K, y^i\right\}_{i=1}^N$; les variables $x$ sont appelées variables explicatives et $K$ est leur nombre. Par exemple, si $K=1$, ils peuvent être le poids ($x_1$) et la taille ($y$) de $N$ personnes différentes; si $K=2$ ils peuvent être le poids ($x_1$), la longueur des pieds ($x_2$) et la taille ($y$) de $N$ personnes différentes.

L'objectif est de déterminer la meilleure relation linéaire possible entre ces grandeurs, c'est-à-dire de déterminer les meilleures valeurs possibles pour les coefficients $\left\{c_j\right\}_{j=0}^K$. En termes mathématiques, cela revient à résoudre le problème de minimisation suivant $$ \left\{c_j\right\}_{j=0}^K = \underset{\tilde{c}_0, \dots, \tilde{c}_k}{argmin} \sum\limits_{i=1}^N \left(y^i - \tilde{c}_0 - \sum\limits_{j=1}^K \tilde{c}_j x_j^i \right)^2$$

S'il existe une relation linéaire entre les données, alors $$y^i = c_0 + \sum\limits_{j=1}^K c_j x_j^i \quad \forall \ i \in \{1, \dots, N\}$$ Cela implique que les coefficients $\left\{c_j\right\}_{j=0}^K$ sont des solutions au système linéaire suivant:

\begin{equation} \begin{pmatrix} 1 & x_1^1 & x_2^1 & \dots & x_K^1 \\ 1 & x_1^2 & x_2^2 & \dots & x_K^2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_1^N & x_2^N & \dots & x_K^N \end{pmatrix} \begin{pmatrix} c_0 \\ c_1 \\ c_2 \\ \vdots \\ c_K \end{pmatrix} = \begin{pmatrix} y^1 \\ y^2 \\ \vdots \\ y^N \end{pmatrix} \end{equation}

Quoi qu'il en soit, comme $N$ dans les applications du monde réel est beaucoup plus grand que $K$, il est très probable que ce système n'admette aucune solution. Ainsi, c'est une approche commun de recourir au calcul d'une solution au sens des moindres carrés; on peut en fait prouver que la solution au sens des moindres carrés est égal à la solution au problème de minimisation quadratique susmentionné, dont dérive le nom de "moindres carrés".

Instructions

e but de l'exercice est de montrer un scénario de cas réel où des solutions des moindres carrés aux systèmes linéaires sont employées; ainsi aucun calcul numérique n'est requis et peu de quantités doivent être correctement insérées.

1. GÉNÉRATION DE DONNÉES: la cellule appelée "GÉNÉRATION DE DONNÉES" est responsable de la génération des données. En particulier, la méthode "Ex3_Chapitre9_12_generate_data" génère les données en superposant du bruit gaussien blanc à des données linéairement dépendantes. Les deux premiers arguments d'entrée régulent l'intensité du bruit. L'argument d'entrée appelée "K" définit le nombre de variables explicatives; les seules valeurs disponibles sont K = 1 et K = 2, de sorte que les données peuvent être visualisées via des nuages de points. Essayez les deux! Finalement, les variables X et Y stockent la matrice de gauche et le vecteur de droite du système linéaire précédemment introduit.

2. INSERTION DE SOLUTION: la cellule appelée "INSERTION DE SOLUTION" vous permet de saisir les valeurs de la matrice de gauche M et du vecteur de droite f, définissant le système linéaire à résoudre afin de calculer la solution souhaitée. Dans ce but, nous rappelons que, étant donné deux matrices A, B:

   • A.T $\rightarrow$ calcule la transposée de A
   • A @ B $\rightarrow$ calcule le produit matriciel entre A et B
   • A * B $\rightarrow$ calcule le produit élément par élément entre A et B

3. VISUALISATION DE LA SOLUTION: la cellule appelée "VISUALISATION DE LA SOLUTION" vous permet de visualiser la solution au problème donnée.

# GÉNÉRATION DE DONNÉES
data, fig = corrections.Ex3_Chapitre9_12_generate_data(0.15, 0.075, K=2)
X = data[0]
Y = data[1]

# INSERTION DE SOLUTION
M =  X.T @ X  # !! inserez ici la matrice !!
f =  X.T @ Y  # !! inserez ici le vecteur de droit !!
sys = M, f

# VISUALISATION DE LA SOLUTION
corrections.Ex3_Chapitre9_12(sys, data, fig)

Coefficients de la solution entrée: (0.0983700703174103, 0.219308350381164, 0.444470734026938)
Coefficients de la solution: (0.0983700703174103, 0.219308350381164, 0.444470734026938)

C'est correct!

Passez au notebook du chapitre 9.13-9.14: La factorisation QR: application à la résolution d'un système au sens du moindres carrées